﻿// Write a program that finds all prime numbers in the range [1...10 000 000]. 
// Use the sieve of Eratosthenes algorithm (find it in Wikipedia).

using System;
using System.Globalization;
using System.Text;

class PrimeNumbersInRangeEratosthenes
{
    static void Main()
    {
        uint range = 10000000;
        bool[] primeNumbersArray = new bool[range];

        // set all numbers to true, because by default they are false
        for (uint i = 2; i < primeNumbersArray.Length; i++)
        {
            primeNumbersArray[i] = true;
        }

        // filter non prime number (set to false)
        for (uint j = 2; j < primeNumbersArray.Length; j++)
        {
            if (primeNumbersArray[j])
            {
                for (uint p = 2; (p * j) < primeNumbersArray.Length; p++)
                {
                    primeNumbersArray[p * j] = false;
                }
            }
        }

        uint primeCount = 0;
        for (int i = 0; i < range; i++)
        {
            if (primeNumbersArray[i])
            {
                primeCount++;
            }
        }

        NumberFormatInfo numberFormatInfo = (NumberFormatInfo)CultureInfo.InvariantCulture.NumberFormat.Clone();
        numberFormatInfo.NumberGroupSeparator = " ";
        Console.WriteLine("The count of prime numbers in range 2 - {0} is: {1}", range.ToString("n0", numberFormatInfo), primeCount);
        Console.Write("Press 'Y' to print all prime numbers in this range or anything else for exit: ");
        string choice = Console.ReadLine();
        if (choice.ToUpper() == "Y")
        {
            // using StringBuilder for better console printing performance
            StringBuilder line = new StringBuilder();
            byte symbolPerLine = 0;
            byte maxSymbolPerLine = 9;
            for (uint i = 0; i < primeNumbersArray.Length; i++)
            {
                if (primeNumbersArray[i])
                {
                    line.Append(i);
                    symbolPerLine++;
                    if (symbolPerLine < maxSymbolPerLine)
                    {
                        line.Append(", ");
                    }

                    if (symbolPerLine == maxSymbolPerLine)
                    {
                        Console.WriteLine(line.ToString());
                        line.Clear();
                        symbolPerLine = 0;
                    }
                }
            }
        }
    }
}